package swordoffer.offer33;

import java.util.Deque;
import java.util.LinkedList;

public class StackSolution {
    public boolean verifyPostorder(int[] postorder) {
        //使用Deque实现单调栈
        Deque<Integer> stack = new LinkedList<>();

        //后续遍历 left right root  逆序 root right left
        //root -> right 为单调递增
        //逆序遍历 后序序列
        int root = Integer.MAX_VALUE;
        for(int i = postorder.length - 1; i >= 0; i--){
            while(!stack.isEmpty() && postorder[i] < stack.peek()){
                root = stack.pop();
            }
            if(postorder[i] > root){
                return false;
            }
            stack.push(postorder[i]);
        }
        return true;
    }
}
